-- The Computer Language Shootout
-- http://shootout.alioth.debian.org/
-- contributed by Mike Pall
-- modified by Sokolov yura

require 'benchmarks/bench'

collectgarbage("setstepmul", 0) -- sometimes it helps much. For this benchmark ~ 10%

local function BottomUpTree(item, depth)
  if depth > 0 then
    local i = item + item
    depth = depth - 1
    local left, right = BottomUpTree(i-1, depth), BottomUpTree(i, depth)
    return { item, left, right }
  else
    return { item } -- Faster for LuaJIT: return { item, false }
  end
end

local function ItemCheck(tree)
  if #tree == 3 then -- Faster for LuaJIT: if tree[2] then
    return tree[1] + ItemCheck(tree[2]) - ItemCheck(tree[3])
  else
    return tree[1]
  end
end

for i = 1,2 do

	local N = tonumber(arg and arg[1]) or 0
	local mindepth = 4
	local maxdepth = mindepth + 2
	if maxdepth < N then maxdepth = N end
	
	do
	  local stretchdepth = maxdepth + 1
	  local stretchtree = BottomUpTree(0, stretchdepth)
	  io.write(string.format("stretch tree of depth %d\t check: %d\n",
	    stretchdepth, ItemCheck(stretchtree)))
	end
	
	local longlivedtree = BottomUpTree(0, maxdepth)
	
	for depth=mindepth,maxdepth,2 do
	  local iterations = 2 ^ (maxdepth - depth + mindepth)
	  local check = 0
	  for i=1,iterations do
	    check = check + ItemCheck(BottomUpTree(1, depth)) +
	            ItemCheck(BottomUpTree(-1, depth))
	  end
	  io.write(string.format("%d\t trees of depth %d\t check: %d\n",
	    iterations*2, depth, check))
	end
	
	io.write(string.format("long lived tree of depth %d\t check: %d\n",
	  maxdepth, ItemCheck(longlivedtree)))

	logPass(i)
end

logEnd()

